package com.zp.self.module.level_4_算法练习.数学.数学推理;

/**
 * @author By ZengPeng
 */
public class 力扣_413_等差数列划分 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_413_等差数列划分().numberOfArithmeticSlices(new int[]{1,2,3,4}));
    }

    /**
    题目：如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
     例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
     给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
     子数组 是数组中的一个连续序列。

    分析：【P 💜💜💜💜】
       1.数学：初始化得到差值,左右指针统计每一段相同差值个数
                根据相同的个数，得到总子集数方程式为： n* (n-1)/2
                --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
       2.动态规划：初始dp[0]=0,dp[1]=0
                从2开始，判断当前节点与前后是否相等，相等时：dp[n]=dp[n-1]+1
                最后累加dp[]
     
    边界值 & 注意点：
       1.
     **/

    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length<3) return 0 ;
        int[] newArr = new int[nums.length-1];
        for (int i = 0; i < newArr.length; i++)//初始化，得到差值
            newArr[i]=nums[i+1]-nums[i];
        int left=0,right=1,sum=0;
        while (right<newArr.length){
            if(newArr[right]!=newArr[right-1]){
                sum+=(right-left)*(right-left-1)/2;
                left=right;
            }
            right++;
        }
        sum+=(right-left)*(right-left-1)/2;
        return sum;
    }

}
